#include <bits/stdc++.h>
using namespace std;
#include "../tools.h"


class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode headpre(-1, head);
        ListNode *p1 = &headpre, *p2 = &headpre;
        while(p2 != nullptr && p2->next != nullptr) {
            p1 = p1->next;
            p2 = p2->next->next;
        }

        stack<ListNode*> st;
        p1 = p1->next;
        while(p1 != nullptr){
            st.push(p1);
            p1 = p1->next;
        }

        p1 = head;
        while(!st.empty()){
            auto node = st.top();
            st.pop();
            node->next = p1->next;
            p1->next = node;
            p1 = node->next;
        }
        p1->next = nullptr; // !!!

    }
};


int main(int argc, char const *argv[])
{
    Solution sol;

    int arr[] = {1,2,3,4};
    int size = sizeof(arr) / sizeof(int);

    
    ListNode* head = create_list(arr, size);

    sol.reorderList(head);

    show(head);

    return 0;
}
